CSE 1729:
Introduction to Principles of
Programming
Programming with Streams
Robert McCartney
Scheduling: final HW
There will be one more homework, due December 8th at 11:59 PM. Note the unusual day (Thursday), but the semester ends on December 9th.
Final exam:
Wednesday, December 14, 6:00 PM-8:00 PM. Here.
Hmm, let’s try something wild
(define (enumerate-integers-from a)
(cons-stream a (enumerate-integers-from (+ a 1))))
> (define test2 (enumerate-integers-from 1))
> (stream-car test2)
1
> (stream-car (stream-cdr test2))
2
> test2
(1 . #
> (cdr test2)
(2 . #
Whoa! How could this work?
(define (enumerate-integers-from a)
(cons-stream a (enumerate-integers-from (+ a 1))))
;; as opposed to
(define (enumerate-integers-from a)
(cons a (enumerate-integers-from (+ a 1))))
;; ?
Whoa! How could this work?
delay and force:
(delay form) packages form (without evaluation) so it can be evaluated
later
(force dform) takes a delayed form and evaluates it.
possible implementation:
(delay form) could be syntactic shorthand for (lambda () form)
in which case force could be implemented as
(define (force form)
(form))
Whoa! How could this work?
Given these:
(cons-stream a b) is syntactically equivalent to
(cons a (delay b))
(define (stream-car str)(car str))
(define (stream-cdr str)(force (cdr str))
However:
cons-stream cannot be a function delay cannot be a function
Code that works for any n?
(define (stream-nth index stream)
(if (= index 1)
(stream-car sequence)
(stream-nth (- index 1)(stream-cdr sequence))))
(define (nth-prime n)
(stream-nth n
(stream-filter prime?
(enumerate-integers-from 2))))
enumerate: integers from 2
filter: prime?
nth: n
Practical considerations
delay and force are defined in R5RS
We will supply definitions for cons-stream, stream- car, and stream-cdr that you can use (although the definitions for stream-car and stream-cdr in these slides would work fine).
✤
✤
Implementation: stream-utils.rkt
;; stream primitives
(define-syntax cons-stream
(syntax-rules ()
((cons-stream head tail)
(cons head (delay tail)))))
(define (stream-car x)
(car x))
(define (stream-cdr x)
(force (cdr x)))
(define empty-stream? null?) ; note name
Utilities from lab
(define (stream-filter f str)
(if (f (stream-car str))
(cons-stream
(stream-car str)
(stream-filter f (stream-cdr str)))
(stream-filter f (stream-cdr str))))
(define (stream-map f str)
(if (null? str)
‘()
(cons-stream (f (stream-car str))
(stream-map f (stream-cdr str)))))
Utilities from lab
(define (stream-nth n stream)
(if (= n 1)
(stream-car stream)
(stream-nth (- n 1) (stream-cdr stream))))
(define (str-to-list str n)
(cond ((or (null? str)(= n 0)) ‘())
(else
(cons (stream-car str)
(str-to-list (stream-cdr str)
(- n 1))))))
(define (scale-stream factor stream)
(stream-map (lambda (x) (* x factor)) stream))
Utilities from lab
(define (add-streams s1 s2)
(cond ((and (null? s1)(null? s2))'())
((null? s1) s2)
((null? s2) s1)
(cons-stream
(+ (stream-car s1)(stream-car s2))
(add-streams (stream-cdr s1)(stream-cdr s2))))
(define (enumerate-integer-stream)
(define (ints-from a)
(cons-stream a (ints-from (+ a 1))))
(ints-from 0))
Add two new symbols
car stream-
cdr
split stream into two
name
build stream from two parts
Build: from streams or values
value
stream
cons- stream
stream
stream
stream
add- streams
stream
value and stream
also: scale-stream
two streams
also: mult-streams append-streams
Implicitly-defined streams
;;; what happens here?
> (define ones (cons-stream 1 ones))
Implicitly-defined streams
;;; what happens here?
> (define ones (cons-stream 1 ones))
> (stream-car ones)
1
> (stream-cdr ones)
Implicitly-defined streams
;;; what happens here?
> (define ones (cons-stream 1 ones))
> (stream-car ones)
1
> (stream-cdr ones)
(1 . #
>
Implicitly-defined streams
;;; what happens here?
> (define ones (cons-stream 1 ones))
> (stream-car ones)
1
> (stream-cdr ones)
(1 . #
> (str-to-list ones 10)
Implicitly-defined streams
;;; what happens here?
> (define ones (cons-stream 1 ones))
> (stream-car ones)
1
> (stream-cdr ones)
(1 . #
> (str-to-list ones 10)
(1 1 1 1 1 1 1 1 1 1)
Implicitly-defined streams
;;; what happens here?
> (define ones (cons-stream 1 ones))
> (stream-car ones)
1
> (stream-cdr ones)
(1 . #
> (str-to-list ones 10)
(1 1 1 1 1 1 1 1 1 1)
1
cons- stream
ones
Implicitly-defined streams
;;; what happens here?
> (define ints (cons-stream 0
(add-streams ones ints)))
Implicitly-defined streams
;;; what happens here?
> (define ints (cons-stream 0
> (stream-car ints)
0
(add-streams ones ints)))
Implicitly-defined streams
;;; what happens here?
> (define ints (cons-stream 0
> (stream-car ints)
0
> (stream-cdr ints)
(1 . #
(add-streams ones ints)))
Implicitly-defined streams
;;; what happens here?
> (define ints (cons-stream 0
> (stream-car ints)
0
> (stream-cdr ints)
(1 . #
> (str-to-list ints 10)
(0 1 2 3 4 5 6 7 8 9)
(add-streams ones ints)))
Implicitly-defined streams
;;; what happens here?
> (define ints (cons-stream 0
> (stream-car ints)
0
> (stream-cdr ints)
(1 . #
> (str-to-list ints 10)
(0 1 2 3 4 5 6 7 8 9)
(add-streams ones ints)))
HOW CAN THIS POSSIBLY WORK???
✤ ✤ ✤
ones ints fib
ones
Walk through on board
0
cons- stream
ints
add- streams
Packaging implicitly-defined streams
;;; write a function that returns an i-d stream
> (define (enumerate-ints)
(define ints
(cons-stream 0 (add-streams ones ints)))
ints)
> (enumerate-ints)
(0 . #
> (str-to-list (enumerate-ints) 5)
(0 1 2 3 4)
Packaging implicitly-defined streams
;;; write a function that returns an i-d stream
> (define (enumerate-ints)
(define ints
(cons-stream 0 (add-streams ones ints)))
ints)
> (enumerate-ints)
(0 . #
Could we use a let here? (define (enumerate-ints)
(let ((ints (cons-stream 0
ints))
(add-streams ones ints))))
Packaging implicitly-defined streams
;;; write a function that returns an i-d stream
> (define (enumerate-ints)
(define ints
(cons-stream 0 (add-streams ones ints)))
ints)
> (enumerate-ints)
(0 . #
Could we use a let here? NO! (define (enumerate-ints)
(let ((ints (cons-stream 0
ints))
(add-streams ones ints))))